package com.wss.lsl.test.driven.arithmetic.heap;

import java.util.Arrays;

/**
 * 堆排序。
 * <P>
 * 堆的结构：最大的元素置于根。
 * </p>
 * 
 * @author sean
 *
 */
public class HeapSort {

	private int[] heap;

	public HeapSort(int[] heap) {
		super();
		this.heap = heap;
	}

	/**
	 * 第一个元素下移，构建堆
	 * 
	 * @param n
	 */
	public void siftdown(int n) {

		int i = 1, c;
		while (true) {
			c = 2 * i;
			if (c > n) {
				break;
			}
			if (c + 1 <= n && heap[c + 1] > heap[c]) {
				c++;
			}
			if (heap[c] <= heap[i]) {
				break;
			}
			swap(i, c);

			i = c;
		}
	}

	/**
	 * 排序
	 */
	public void sort() {
		// 构建堆
		for (int i = 2; i < heap.length; i++) {
			siftup(i);
		}

		// 排序
		for (int i = heap.length - 1; i > 1; i--) {
			swap(1, i);
			siftdown(i - 1);
		}
	}

	/**
	 * 校验数组的顺序性
	 */
	public void validateSort() {
		for (int i = 2; i < heap.length; i++) {
			if (heap[i - 1] > heap[i]) {
				throw new RuntimeException("数组不是有序的");
			}
		}
	}

	/**
	 * 校验堆性质
	 */
	public void verifyHeap() {
		for (int i = heap.length - 1; i > 1; i--) {
			if (heap[i / 2] < heap[i]) {
				throw new RuntimeException("无效的堆");
			}
		}
	}

	/**
	 * 元素上移，构建堆
	 * 
	 * @param i
	 */
	public void siftup(int i) {

		int p;
		for (; i > 1 && heap[(p = i / 2)] < heap[i]; i = p) {
			swap(i, p);
		}
	}

	private void swap(int i, int j) {

		int t = heap[i];
		heap[i] = heap[j];
		heap[j] = t;
	}

	public String toString() {
		return Arrays.toString(heap);
	}
}
